/*************************************************************************
	> File Name: 235.二叉搜索树的最近公共祖先.c
	> Author: Maureen 
	> Mail: Maureen@qq.com 
	> Created Time: 三  9/15 12:55:12 2021
 ************************************************************************/

/*
 * 【思路】一次遍历。利用二叉搜索树的性质，分为三种情况：
 * 1. 如果当前节点大于 `p` 和 `q` 的值，则 `p` 和 `q` 的最近公共祖先在当前节点的左子树；
 * 2. 如果当前节点小于 `p` 和 `q` 的值，则 `p` 和 `q`的最近公共祖先在当前节点的右子树；
 * 3. 如果上述情况都不满足，则当前节点就是"分岔节点"，此时要么 `p`和 `q` 在当前节点的不同子树中，要么其中一个节点就是当前节点。
 */

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    struct TreeNode *ancestor = root;
    while (true) {
        if (ancestor->val > p->val && ancestor->val > q->val) {
            ancestor = ancestor->left;
        } else if (ancestor->val < p->val && ancestor->val < q->val) {
            ancestor = ancestor->right;
        } else {
            break;
        }
    }
    
    return ancestor;
}
